1. Field of the Invention
The present invention relates to an image compression system, and more particularly to a high speed code word detecting apparatus and method using a cascade structure which makes it possible to detect a code word having a variable length according to a successive bit stream encoded using a run-length encoding method.
2. Description of the Prior Art
In general, because it includes a large amount of information, motion picture image data requires a significantly large memory space, bandwidth, and high speed throughput for carrying out the steps of storing, transmitting or processing. Thus, an appropriate, affordable and distortion free image compression technology is virtually required for storage and transmission transmission.
Such a data compression technology is focused on restoration of data. For that reason there is employed a variable length encoding method which is frequently applied for a lossless compression. In a variable length encoding method, a fixed length data is converted into a variable length code depending on a statistical characteristic of the data.
Variable length encoding a short code word for frequently generated data and a long code word is allocated for data occuring less frequency.
Therefore, when a variable length code word is allotted in a library of every possible source code word, the length of an average code word of a variable length code becomes much shorter than that of an average code word length of the source data, whereby data compression is achieved. At this time, according to a statistical characteristic of the data, there is employed a Huffman coding method for a variable length code.
As shown in FIG. 1, a conventional bit packing apparatus includes: an adder 10 for adding an applied code length value to a modulo value obtained by subtracting a packing bit length from a previous code length value; a comparator 11 for comparing an output value of the adder 11 and the size value of the packing bit PB and outputting a control signal; a modulo operator 12 for dividing an output value of the adder by packing bit PB and determining the remainder value; a first multiplexer 13 for outputting a packing bit PB which is a remainder value and is outputted from the modulo operator 12 and which is selected from a plurality n of packing bits PB11-PB1n which sequentially decrease by a certain amount of bits; a second multiplexer 14 for outputting a packing bit PB which is a remainder value and is outputted from the modulo operator 12 and which is selected from a plurality n of packing bits PB21-PB2n which are sequentially increased by a certain amount of bits; an OR gate 15 for ORing a packing bit PB outputted from the first multiplexer 13 and a remainder bit RB; a third multiplexer 16 for converting to a new remainder bit RB a packing bit PB outputted from the OR gate 15 or a packing bit PB outputted from the second multiplexer 14, in accordance with the control signal of the comparator 11; and a flipflop 17 for latching and outputting a full packing bit PB outputted from the OR gate 15, in accordance with a control signal of the comparator 11. The detailed composition of the first and second multiplexers 13, 14 is illustrated in FIG. 2.
The operation of the thusly constituted conventional bit packing apparatus will now be described with reference to the accompanying drawings.
First, when a codeword and a code length are simultaneously applied, if the codeword is "11011", the code length is "5", and the data for packing is 8 bits, the data arrayed in order from the most significant bit becomes "1101 1000".
At this time, the adder 10 adds the remainder value obtained by subtracting a packing bit from a previous code length, to a serially applied code length. The modulo operator 12 determines a remainder value by dividing the output value of the adder 10 by the packing bit PB to thereby decide the size of a codeword which is to be applied to a next packing bit.
The number of bits in the output from the modulo operator 12, counted from the significant bit, is defined by the the remainder value, so that there is required a next packing data obtained by subtracting the remainder bits from the packing bits.
Therefore, the first multiplexer 13 outputs a packing bit PB serving as a remainder value outputted from the modulo operator 12 from among the packing bits PB11-PB1n having pointer values decreased sequentially by a certain amount of bits, whereas the second multiplexer 14 outputs a packing bit PB serving as a remainder value outputted from the modulo operator 12 from among the packing bits PB21-PB2n having pointer values increased sequentially by a certain amount of bits.
When a code word as shown in FIG. 3A is applied, the first multiplexer 13 selects a corresponding bit among packing bits PB1n-PB1n, as shown in FIG. 3B, and outputs the selected bit to the OR gate 15; the second multiplexer 14 selects a corresponding bit among packing bits PB2n-PB2n, as shown in FIG. 3C, and outputs the selected bit to the third multiplexer 16.
At this time, the comparator 11 compares an output value of the adder 10 and the packing bit PB, so that when the output of the adder 10 is equal to or larger than that of the packing bit PB, a control signal of "1" is outputted, and when the output of the adder 10 is less than that of the packing bit PB, a control signal of "0" is outputted.
In accordance with this control signal outputted from the comparator 11, the third multiplexer 16 selects an output value of the OR gate 15 or an output value of the second multiplexer 14 to thereby output a remainder bit RB, and the OR gate 15 ORs the output value of the first multiplexer 13 and the output value of the third multiplexer 16 so that the present packing bit and remainder bit RB are ORed to thereby output a certain size of packing bits.
For example, assuming that the number of packed bits are eight, remainder bits RB are "1100 0000", and present packing bits are "0000 1010", the OR gate 15 serves to output packed bits "1100 1010" by an OR operation.
Using the same steps as described above, the third multiplexer 16, according to the control signal of the comparator 11, selects an output value of the OR gate 15 or an output value of the second multiplexer 14 to repeatedly generate a remainder bit RB, and the newly generated remainder bits RB are ORed with an output value of the first multiplexer 13 at the OR gate 15 to thereby output a certain amount of packed bits.
At this time, a variable length coding has an irregular code length. Therefore, in order to store and transmit a serial bit stream, the data should be held in a buffer until the data buffer becomes full or overflows.
As a result, the flipflop 17 holds the data until the comparison signal outputted from the comparator 11 becomes "1", that is to say, when the packing bits outputted from the OR gate 15 become full, the held packing bits are outputted.
As described above, the conventional bit packing apparatus randomly selects the number of bits which are to be packed, and in a formatter of a high picture quality VCR, the selectedly fixed bits can be recorded in a memory device having an 8-bit or 16-bit word length as well as accessed therefrom. Also, the length of a code word can be easily varied using a much smaller number of packing bits.
However, the conventional bit packing apparatus does not determine a code word per input unit applied thereto once a cycling time, so that a maximum code length should be allocated thereto, and thus the apparatus is not suitable.